package zcw.com.lib_leet_code;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

import zcw.com.lib_leet_code.util.Util;

/**
 * Created by 朱城委 on 2021/9/8.<br><br>
 *
 * 中等：合并区间
 */
public class Topic56 {

    public static void main(String[] args) {
        Topic56 instance = new Topic56();

        int[][] array = new int[][] {{1,3},{2,6},{8,10},{15,18}};
        Util.printArray(instance.merge(array));

        array = new int[][] {{1,4},{4,5}};
        Util.printArray(instance.merge(array));

        array = new int[][] {{1,4},{0,4}};
        Util.printArray(instance.merge(array));

        array = new int[][] {{2,3},{4,5},{6,7},{8,9},{1,10}};
        Util.printArray(instance.merge(array));
    }

    public int[][] merge(int[][] intervals) {
        if(intervals.length < 2) {
            return intervals;
        }

        Arrays.sort(intervals, (o1, o2) -> o1[0] - o2[0]);

        List<int[]> result = new ArrayList<>();
        for(int[] sub : intervals) {
            int start = sub[0];
            int end = sub[1];

            int size = result.size();
            if(size == 0 || result.get(size - 1)[1] < start) {
                result.add(new int[] {start, end});
            }
            else {
                result.get(size - 1)[1] = Math.max(result.get(size - 1)[1], end);
            }
        }

        return result.toArray(new int[result.size()][2]);
    }

    public int[][] merge2(int[][] intervals) {
        if(intervals.length < 2) {
            return intervals;
        }

        Arrays.sort(intervals, (o1, o2) -> o1[0] - o2[0]);

        int count = 1;
        for(int i = 1; i < intervals.length; i++) {
            helper(i, intervals, intervals[i]);

            count = intervals[i][0] == -1 ? count : count + 1;
        }

        int[][] result = new int[count][2];
        count = 0;
        for (int[] interval : intervals) {
            if (interval[0] != -1) {
                result[count++] = interval;
            }
        }

        return result;
    }

    private void helper(int end, int[][] intervals, int[] sub) {
        for(int i = 0; i < end; i++) {
            if(intervals[i][0] == -1) {
                continue;
            }

            if(sub[0] > intervals[i][1] || sub[1] < intervals[i][0]) {
                continue;
            }

            intervals[i][0] = Math.min(sub[0], intervals[i][0]);
            intervals[i][1] = Math.max(sub[1], intervals[i][1]);

            sub[0] = -1;
            sub[1] = -1;
        }
    }
}
